/*
题目: 计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

https://leetcode.cn/problems/count-of-smaller-numbers-after-self
 */
public class CountSmaller {
    int[] src = null;
    int[] index = null;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        src = new int[n];  // 记录答案

        // 核心思路 : 创建 Index 数组, 对 Index 数组进行排序, 排序过程中根据相对位置计算 src
        index = new int[n]; // 下标
        for (int i = 0; i < n; i++) index[i] = i;

        mergeSort(nums, 0, n - 1);

        List<Integer> ret = new ArrayList<> ();
        for (int i = 0; i < n; i++)
            ret.add(src[i]);
        return ret;
    }

    private void mergeSort(int[] nums, int start, int end) {
        if (start == end) {
            return ;
        }

        int mid = start + ((end - start) >> 1);
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);

        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int start1 = start;
        int start2 = mid + 1;
        int end1 = mid;
        int end2 = end;
        int[] tmpArr = new int[end - start + 1];
        int k = 0;

        // 下标数组跟着排序, nums 某个元素的下标就是 reflect 的下标
        while (start1 <= end1 && start2 <= end2) {
            if (nums[index[start1]] <= nums[index[start2]]) {
                tmpArr[k] = index[start1];
                // 计算单个元素的 src
                src[index[start1]] += start2 - mid - 1;
                start1 ++;
            } else {
                tmpArr[k] = index[start2];
                start2 ++;
            }
            k++;
        }

        while (start1 <= end1) {
            // 计算单个元素的 src
            src[index[start1]] += start2 - mid - 1;
            tmpArr[k ++] = index[start1 ++];
        }
        while (start2 <= end2) {
            tmpArr[k ++] = index[start2 ++];
        }

        for (int i = 0; i < k; i++) {
            index[start + i] = tmpArr[i];
        }
    }
}
